//
// Description: 287. 寻找重复数
// Created by Loading on 2022/5/2.
//

#include <bits/stdc++.h>

using namespace std;

/* Floyd 判圈算法 */
int findDuplicate(vector<int> &nums) {
    /* 将下标与数值映射，一定存在环，快慢指针，寻找环的起点 */
    int slow = 0, fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    /* 将一个指针放回起点，同速移动，相遇位置即为环的入口，也即为答案 */
    slow = 0;
    while (nums[slow] != nums[fast]) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return nums[slow];
}

int main() {
    vector<int> nums{1, 3, 4, 2, 2};
    int res = findDuplicate(nums);
    cout << res << endl;

    return 0;
}